HW#4 --- last modified March 02 2019 21:25:40..

Solution set.

Due date: Apr 24

Files to be submitted:
  Hw4.tex
  Prime.zip

Purpose:To learn about computer algebra and number theoretic algorithms

Specification:

First, do the following problems out of CLRS and submit them in Hw4.tex : 31.1-7, 31.2-4, 31.5-1, 31.7-3.

Then I would like you to write a java program Prime.java which will be run from the command line with a line like:

java Prime file.txt confidence

Here the command line argument file.txt is the name of a file whose contents will be read by your program; the command line argument confidence is supposed to be an integer such that the odds of failure of your algorithms are less than 2^-confidence. Your program should read out of this file a sequence of ASCII digits between 0-9 which represent some number which might be a prime number. This sequence of digits with be hundreds of characters long. Your program then runs your implementation of the Miller-Rabin algorithm from page 892. This algorithm will be quite challenging to implement. If you are not already working in a group, it is strongly advised you join a group in order to have some chance of completing this project. Fortunately, the implementation of the algorithm can be split into several testable subgoals which I can give partial credit for. You can implement each of these separate subgoals in a class by itself and submit the whole project as Prime.zip. The classes I would like to see are ToBinary, ToDecimal, Multiply, Add, Subtract, Divide, Mod, ModularExponentiation. Each class should have public methods which can be used by the other classes if needed. In addition, each class should have a main which can be used to test it from the command line. A specification for how each class should act on the command line is described below:

ToBinary: If run with a line like:

java ToBinary file.txt

ToBinary should read a sequence of ASCII digits between 0-9 from file.txt and it should output the ASCII for the corresponding binary number. It should work for files containing hundred or thousands of digits.

ToDecimal: If run with a line like:

java ToDecimal file.txt

ToDecimal should read a sequence of ASCII binary digits (either 0 or 1) from file.txt and it should output the ASCII for the corresponding decimal number. It should work for files containing hundred or thousands of digits.

Add: If run with a line like:

java Add file1.txt file2.txt

Add should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It should then output a sequence of ASCII binary digits which is the result of adding these two numbers. It should work for files containing hundred or thousands of digits.

Subtract: If run with a line like:

java Subtract file1.txt file2.txt

Subtract should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It should then output a sequence of ASCII binary digits which is the result of subtracting these two numbers. It should work for files containing hundred or thousands of digits.

Multiply: If run with a line like:

java Multiply file1.txt file2.txt

Multiply should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It should then output a sequence of ASCII binary digits which is the result of multiplying these two numbers. It should work for files containing hundred or thousands of digits.

Multiply: If run with a line like:

java Divide file1.txt file2.txt

Divide should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It should then output a sequence of ASCII binary digits which is the result of dividing these two numbers (number of file1 divided by number of file 2). It should work for files containing hundred or thousands of digits.

Mod: If run with a line like:

java Mod file1.txt file2.txt

Mod should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It should then output a sequence of ASCII binary digits which is the result of modding these two numbers (number of file1 mod the number of file2). It should work for files containing hundred or thousands of digits.

ModularExponentiation: If run with a line like:

java ModularExponentiation file1.txt file2.txt file3.txt

ModularExponentiation should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt and file3.txt. Let x, y, z denote respectively the numbers parsed out of file1, file2, and file3. It should then output a sequence of ASCII binary digits which is the result of x^y mod z. It should work for files containing hundred or thousands of digits.

Point Breakdown